#pragma once

#include<fstream>
#include"Huffman.h"
#include<string>
#include<assert.h> 
using namespace std;


struct CharInfo
{
    char ch;//字符
    long long count;//出现次数
    string code;//字符编码

    CharInfo operator+(const CharInfo& info)
    {
        CharInfo tmp;
        tmp.count = count + info.count;
        return tmp;
    }
    bool operator>(const CharInfo&info)const
    {
        return count > info.count;
    }

    bool operator!=(const CharInfo&info)
    {
        return count != info.count;
    }
};

class FileCompress
{
    typedef HuffmanTreeNode<CharInfo> HTNode;
public:
    //只存放字符和count用于压缩时写入(code不需要)
    struct CacheInfo
    {
        char ch;
        long long count;
    };

    //哈希数组每个位置都初始化
    FileCompress()
    {
        for (size_t i = 0; i < 256; ++i)
        {
            HashInfos[i].ch = i;
            HashInfos[i].count = 0;
        }
    }


    void Compress(const char*file)
    {
        //1.统计文件出现次数,ifstream输入方式打开，是从源文件取，将内容写到其他地方的方式
        ifstream ifs(file, ios_base::in | ios_base::binary);//自动关闭，打开失败抛异常
        char ch;
        while (ifs.get(ch))//ifs >> ch
        {
            ++HashInfos[ch].count;
        }

        //2.生成Huffman树

        //flag标识是否有效
        CharInfo flag;
        flag.count = 0;

        //根据HashInfos数组的值生成HafumanTree
        HuffmanTree<CharInfo> tree(HashInfos, 256, flag);//大根堆的树

        //3.每个树的节点转换出haffman编码0或1
        ConvertHuffmanCode(tree.GetRoot());

        //4.压缩
        string compressfile = file;

        //创建.huffman文件，用ofs指向
        compressfile += ".huffman";
        ofstream ofs(compressfile.c_str(), ios_base::out | ios_base::binary);

        //5.向压缩文件写入字符和出现次数，方便解压缩从该文件重建huffman树
        for (size_t i = 0; i < 256; ++i)
        {
            if (HashInfos[i].count > 0)
            {
                CharInfo info;
                info.ch = HashInfos[i].ch;
                info.count = HashInfos[i].count;
                ofs.write((char*)&info, sizeof(CacheInfo));
            }
        }
        //在文件结尾加入文件写入完毕的标识
        CacheInfo end;
        end.count = 0;
        ofs.write((char*)&end, sizeof(CacheInfo));

        //开始压缩，根据_hashInfo内字符的huffman编码写入value，并满一字节就写入到文件
        ifs.clear();
        ifs.seekg(0);
        char value = 0;
        int pos = 0;
        while(ifs.get(ch))
        {
            string code = HashInfos[(unsigned char)ch].code;
            for (size_t i = 0; i < code.size(); ++i)
            {
                if (code[i] == '0')
                    value &= ~(1 << pos);
                else if (code[i] == '1')
                    value |= (1 << pos);
                else
                    assert(false);
                ++pos;
                //满足8位一字节就写入到文件里

                if (pos == 8)
                {
                    ofs.put(value);
                    printf("%x\n", value);
                    pos = 0;
                    value = 0;
                }
            }
        }
        //表示如果最后的编码没构成一个字节需单独处理
        if (pos > 0)
        {
            ofs.put(value);
            printf("%x\n", value);
        }

    }


    //5.解压缩
    void UnCompress(const char*file)
    {
        //打开压缩文件解压缩，并去掉后缀并改为.unhuffman
        ifstream ifs(file, ios_base::in | ios_base::binary);
        string uncompressfile = file;
        //rfind，找不到就返回npos，size_t的最大值
        size_t pos=uncompressfile.rfind('.');
        assert(pos != string::npos);
        uncompressfile.erase(pos);

#ifdef _DEBUG
        uncompressfile += ".unhuffman";
#endif

        ofstream ofs(uncompressfile.c_str(),ios_base::out|ios_base::binary);

        //从文件读到info，对应到HashInfos数组
        while(1)
        {
            CacheInfo info;
            ifs.read((char*)&info, sizeof(CacheInfo));
            if (info.count > 0)
                HashInfos[(unsigned char)info.ch].count = info.count;
            else
                break;
        }

        CharInfo flag;
        flag.count = 0;
        //根据HashInfos数组创建哈夫曼树tree对象，tree内生成哈夫曼二叉树
        HuffmanTree<CharInfo> tree(HashInfos, 256, flag);
        //解压缩
        HTNode*root = tree.GetRoot();
        HTNode*cur = root;
        //根节点的count是所有字符出现次数的和
        long long AllCount = root->_w.count;
        char ch;
        //读一个字符，判断字符每个位是0还是1，并根据0,1向左右走
        //每走一次判断节点是否是叶子结点，如果是则把对应的字符写入解压缩的文件
        //不是则走下一次，判断是向左还是右直到叶子结点
        while (ifs.get(ch))
        {
            for (size_t i = 0; i < 8; ++i)
            {
                if ((ch & (1 << i))!=0)
                    cur = cur->_right;
                else
                    cur = cur->_left;

                if (cur->_left == NULL
                    && cur->_right == NULL)
                {
                    ofs.put(cur->_w.ch);
                    cur = root;
                    if (--AllCount == 0)
                        return;
                }
            }
        }
    }


    //生成huffman编码
    //方法一
    void ConvertHuffmanCode(HTNode* root)
    {
        if (root == NULL)
            return;
        //找到叶子，倒着向上给数据编码
        if (root->_left == NULL && root->_right == NULL)
        {
            string &code = HashInfos[(unsigned char)root->_w.ch].code;
            HTNode*cur = root;
            HTNode* parent = cur->_parent;
            while (parent != NULL)
            {
                if (cur == parent->_left)
                    code += '0';
                else
                    code += '1';
                cur = parent;
                parent = parent->_parent;
            }
            reverse(code.begin(), code.end());
        }
        ConvertHuffmanCode(root->_left);
        ConvertHuffmanCode(root->_right);
    }
    //方法二
    /*void ConvertHuffmanCode(HTNode*root)
    {
    if (root == NULL)
    return;

    if (root->_left == NULL && root->_right == NULL)
    {
    HashInfos[(unsigned char)root->_w.ch].code = root->_w.code;
    return;
    }

    if (root->_left != NULL)
    {
    root->_left->_w.code = root->_w.code + '0';
    ConvertHuffmanCode(root->_left);
    }

    if (root->_right != NULL)
    {
    root->_right->_w.code = root->_w.code + '1';
    ConvertHuffmanCode(root->_right);
    }
    }*/

private:
    CharInfo HashInfos[256];
};

//先压缩文件
void _FileCompress()
{
    FileCompress FC;
    FC.Compress("I have a dream.txt");
}

//再解压文件
void _FileUnCompress()
{
    FileCompress FC;
    FC.UnCompress("I have a dream.txt.huffman");
}